#pragma once
#include <vector>
#include <set>
#include <deque>
#include <cstdio>

enum BoatSide
{
	BoatSideLeft,
	BoatSideRight,
};

struct cross
{
	BoatSide side;
	int monsterCount;
	int playerCount;
};

struct status
{
	BoatSide side;
	int leftMonsterCount;
	int leftPlayerCount;
	int rightMonsterCount;
	int rightPlayerCount;

	void Show()
	{
		printf("status: %d,%d|%d,%d\n", leftMonsterCount, leftPlayerCount,
			rightMonsterCount, rightPlayerCount);
	}

	int GetKey()
	{
		return side * 10000 + leftMonsterCount * 1000 + leftPlayerCount * 100
			+ rightMonsterCount * 10 + rightPlayerCount;
	}

	void SwitchDir()
	{
		if (side == BoatSideLeft)
		{
			side = BoatSideRight;
		}
		else
		{
			side = BoatSideLeft;
		}
	}

	void Init()
	{
		side = BoatSideLeft;
		leftMonsterCount = 3;
		leftPlayerCount = 3;
		rightMonsterCount = 0;
		rightPlayerCount = 0;
	}

	bool IsDone()
	{
		return rightMonsterCount == 3 && rightPlayerCount == 3;
	}

	bool CanCross(cross c)
	{
		if (c.side == BoatSideLeft)
		{
			if (leftMonsterCount < c.monsterCount
				|| leftPlayerCount < c.playerCount)
			{
				return false;
			}
			if (leftPlayerCount - c.playerCount > 0 && leftMonsterCount - c.monsterCount > leftPlayerCount - c.playerCount)
			{
				return false;
			}
		}
		else
		{
			if (rightMonsterCount < c.monsterCount
				|| rightPlayerCount < c.playerCount)
			{
				return false;
			}
			if (rightPlayerCount - c.playerCount > 0 && rightMonsterCount - c.monsterCount > rightPlayerCount - c.playerCount)
			{
				return false;
			}
		}

		return true;
	}

	bool IsValid()
	{
		return leftMonsterCount <= leftPlayerCount && rightMonsterCount <= rightPlayerCount;
	}

	void Cross(cross c)
	{
		if (c.side == BoatSideLeft)
		{
			leftMonsterCount -= c.monsterCount;
			rightMonsterCount += c.monsterCount;
			
			leftPlayerCount -= c.playerCount;
			rightPlayerCount += c.playerCount;
		}
		else
		{
			leftMonsterCount += c.monsterCount;
			rightMonsterCount -= c.monsterCount;

			leftPlayerCount += c.playerCount;
			rightPlayerCount -= c.playerCount;
		}
		SwitchDir();
	}
};

struct statusNode
{
	statusNode* parent;
	status s;
};

class CrossRiver
{
public:
	void Init();

	void Do();

private:
	void _Dfs(status s);
	void _Bfs();
	void ShowCrossPath();
	void ShowStatusLinkPath(statusNode* node);

private:
	std::set<int> memo;
	std::vector<cross> crossPath;
	std::vector<status> statusPath;
	status begin;
};